from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-27. 移除元素
    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。
    元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

    假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

    更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
    返回 k。
    """

    def removeElement(self, nums: List[int], val: int) -> int:
        """
        :param nums:
        :param val:
        :return:
        思路：双指针，两个指针分别指向首、尾，即左、右；
        当左指针的元素==val，则左指针递增1，即占位1；
        如果右指针的元素，被替换成左指针==val的值，则右指针递减1；
        直到左右指针相遇，即排查完所有的元素
        """
        right = len(nums) - 1
        left = 0
        while left <= right:
            if nums[left] == val:
                if nums[right] != val:
                    temp = nums[right]
                    nums[right] = nums[left]
                    nums[left] = temp
                    left += 1
                right -= 1
            else:
                left += 1
        return left

    def removeElement_2(self, nums: List[int], val: int) -> int:
        """
        :param nums:
        :param val:
        :return:
        思路：双指针，两个指针分别指向首、尾，即左、右；
        当右指针的元素==val，则右指针递减1；
        如果右指针元素！=val，这个要作为预备替换给左指针，保留元素，判断左指针元素：
           如果左指针元素！=val，则左指针递增1，即占位1，右指针不变，预备给下一次
           如果左指针元素==val，则右指针元素替换给左指针，右指针再递减1，左指针再递增1（即占位）
        """
        right = len(nums) - 1
        left = 0
        while left <= right:
            if nums[right] == val:
                right -= 1
            else:
                if nums[left] == val:
                    temp = nums[right]
                    nums[right] = nums[left]
                    nums[left] = temp
                    right -= 1
                left += 1
        return left

    def removeElement_daan(self, nums: List[int], val: int) -> int:
        """
        看完官方解答1后的修改
        :param nums:
        :param val:
        :return:
        思路理解：双指针，两个指针都从开头开始指，只有当符合条件的，才会占位一个左指针，不符合条件的，左指针不变，也就是没有占位；
        右指针控制查找下一个元素，所以右指针一直向右递增移动，直到右指针遍历完所有元素
        """
        right = 0
        left = 0
        i = 0
        while i < len(nums):
            if nums[right] != val:
                nums[left] = nums[right]
                left += 1
            right += 1
            i += 1
        return left

    def removeElement_20250717(self, nums: List[int], val: int) -> int:
        """
        :param nums:
        :param val:
        :return:
        题解思路：歪打正着，意外的答案
        但是用各种情况推敲后，发现可以实现，没有bug，提交审核也通过了。
        但是，这种解法，思路不清晰，不推荐。
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            if nums[left] == val:
                nums[left] = nums[right]
                right -= 1
            else:
                left += 1
        return left

    def removeElement_20250724(self, nums: List[int], val: int) -> int:
        """
        :param nums:
        :param val:
        :return:
        题解思路：
        双指针，
        left控制记录有效的值，right控制往右移动
        """
        left = 0
        right = 0
        while right < len(nums):
            if nums[right] != val:
                nums[left] = nums[right]
                left += 1
            right += 1
        return left

    def removeElement_review_20250729(self, nums: List[int], val: int) -> int:
        """
        解题思路：左右指针控制，左指针对应有效值，右指针遍历
        """
        n = len(nums)
        left = 0
        right = 0
        while right < n:
            if nums[right] != val:
                nums[left] = nums[right]
                left += 1
            right += 1
        return left

    def removeElement_review_20250731(self, nums: List[int], val: int) -> int:
        """
        解题思路：左右指针控制，左指针对应有效值，右指针遍历
        """

if __name__ == '__main__':
    s = Solution()

    nums = [3, 2, 2, 3]
    # val = 3
    # nums = [0, 1, 2, 2, 3, 0, 4, 2]
    val = 2
    # k = s.removeElement_20250724(nums, val)
    k = s.removeElement_review_20250729(nums, val)
    print('val:', val, 'k:', k, 'nums:', nums)
